package com.pan.alg.niuke.link;

import java.util.List;

import static java.util.Collections.swap;

/**
 * 给定一个节点数为n的无序单链表，对其按升序排序。
 *
 * 数据范围：0 < n \le 1000000<n≤100000
 * 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 * 实际考察的是快速排序
 */
public class SortLinkList {

    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public static ListNode sortInList (ListNode head) {
        // write code here
        //将链表转化为数组
        List<ListNode> arrLink = ListNodeUtil.transListNode2List(head);

        List<ListNode> sortedListNode = quickSortListNode(arrLink,0,arrLink.size()-1);

        ListNode sortedNode = ListNodeUtil.transListNode2LinkNode(sortedListNode);

        return sortedNode;
    }

    public static List<ListNode> quickSortListNode(List<ListNode> arrLink, int l, int r) {
        if(l>=r){
            return arrLink;
        }

        int index = partion(arrLink,l,r);

        quickSortListNode(arrLink,l,index-1);
        quickSortListNode(arrLink,index+1,r);

        return arrLink;
    }

    public static int partion(List<ListNode> arrLink, int l, int r) {

        ListNode compare = arrLink.get(l);
        int lastMin = l;
        for (int i = l+1; i <=r ; i++) {
            if(arrLink.get(i).val<compare.val){
                lastMin++;
                swap(arrLink,i,lastMin);
            }
        }
        swap(arrLink,l,lastMin);
        return lastMin;
    }

    public static void main(String[] args) {
        int[] arr = {-426572,-406609,724427,-157789,-132713,720732,-39078,-348926,-693458,559374,114739,-748249,428207,-767407,401563,646432,-682870,483610,-608888,94840,749542,359115,131739,935294,347325,80573,-869091,-757897,-860166,-227942,-484068,-170790,-362441,-860466,819197,817675,886101,463504,-100482,496406,-860791};
        ListNode listNode = ListNodeUtil.transArr2List(arr);
        ListNode listNode1 = sortInList(listNode);
        ListNodeUtil.printListNode(listNode1);

    }

}
